1. Field of the Invention
The present invention relates to a method of performing parallel search optimization for a computerized process. Particularly, the method allows for avoidance of the ill-conditioning problem for matrix-based computerized processes in model predictive controllers.
2. Description of the Related Art
In numerical analysis, the condition number associated with a problem is a measure of that problem's amenability to digital computation; i.e., how numerically well-posed the problem is. A problem with a low condition number is said to be “well-conditioned”, while a problem with a high condition number is said to be “ill-conditioned”.
For example, the condition number associated with the linear equation Ax=b gives a bound on how inaccurate the solution x will be after approximate solution. It should be noted that this is before the effects of round-off error are taken into account. Conditioning is a property of the matrix, not the algorithm or floating point accuracy of the computer used to solve the corresponding system. In particular, the condition number is, to a rough estimate, the rate at which the solution x will change with respect to a change in b. Thus, if the condition number is large, even a small error in b may cause a large error in x. Conversely, if the condition number is small, then the error in x will not be much bigger than the error in b.
The condition number is defined more precisely to be the maximum ratio of the relative error in x divided by the relative error in b. Letting e be the error in b, then the error in the solution A−1b is A−1e. The ratio of the relative error in the solution to the relative error in b is:
                                                  A                          -              1                                ⁢          e                            /                                            A                          -              1                                ⁢          b                                                    e                    /                      b                      .This may be transformed to:
                                    A                      -            1                          ⁢        e                                e              ·                            b                                                          A                          -              1                                ⁢          b                              .  The maximum value (for nonzero b and e) k is given by the product of the two operator norms, k(A)=∥A−1∥·∥A∥. The same definition is used for any consistent norm. This number is referred to as the condition number of a matrix.
Condition numbers for singular-value decompositions, polynomial root findings, eigenvalues and many other problems may be defined. Generally, if a numerical problem is well-posed, the problem can be expressed as a function f mapping its data, which is an m-tuple of real numbers x, into its solution, with an n-tuple of real numbers f(x).
Its condition number is then defined to be the maximum value of the ratio of the relative errors in the solution to the relative error in the data, over the problem domain:
      max    ⁢          {                                                                                                f                  ⁡                                      (                    x                    )                                                  -                                  f                  ⁡                                      (                                          x                      *                                        )                                                                              f                ⁡                                  (                  x                  )                                                                          /                                                                x                -                                  x                  *                                            x                                                  :                                                        x              -                              x                *                                                          <          ɛ                    }        ,where ε is some reasonably small value in the variation of data for the problem. If f is also differentiable, then the above is approximately:
                                  f          ′                ⁡                  (          x          )                            f        ⁡                  (          x          )                          ·                  x              .  
The present invention is particularly directed towards model predictive control (MPC), which represents a family of model-based controllers. These controllers are used to manipulate process inputs to move the outputs of the process to be controlled to some desired targets. MPC controllers use the model of the process to be controlled to predict its future behavior. The future model outputs are calculated from the model:Y=AUwhere Y is an N×1 vector for the future outputs, A is an N×M matrix of the parameters representing the process model, and U is an M×1 vector representing future inputs. To find the future inputs U that will move the process outputs Y closer to their target output R, the following equation is used:U=(ATA)−1AT(R−Y)
This inverse-based controller becomes sensitive to input uncertainties and plant-model mismatch, along with co-linear outputs. The matrix AT A may be ill-conditioned, which will result in large control inputs U. This ill-conditioning has to be checked at each sampling time and a corrective action has to be taken before inverting the matrix. Typical methods used for controlling this problem include the Singular Value Thresholding (SVT) technique and Move Suppression (MS) methods. The SVT method involves discarding the singular values of the process model below a certain threshold. This method solves the ill-conditioning problem at the expense of neglecting the smallest singular values. The MS method is an ad hoc method, where the magnitude of the diagonal elements of the matrix AT A to be inverted are increased, removing the ill-conditioning.
Although effective, there is a need for a better method for checking for ill-conditioning at each sampling time and taking a corrective action before inverting the matrix in a model predictive controller. Thus, a method of performing parallel search optimization solving the aforementioned problems is desired.